package LeetCode.month01.day18;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class No236 {
    HashMap<Integer,TreeNode> parent = new HashMap<>();
    Set<Integer> visited = new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p!=null){
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while(q!=null){
            if(visited.contains(q.val))
                return q;
            q= parent.get(q.val);
        }
        return null;
    }

    public void dfs(TreeNode root){
        if(root==null) return;
        if(root.left!=null){
            parent.put(root.left.val,root);
            dfs(root.left);
        }
        if(root.right!=null){
            parent.put(root.right.val,root);
            dfs(root.right);
        }
    }




//    TreeNode ans;
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        dfs(root,p,q);
//        return ans;
//    }
//
//    public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
//        if(root ==null) return false;
//        boolean lson = dfs(root.left,p,q);
//        boolean rson = dfs(root.right,p,q);
//        if((lson||rson)&&((root.val==p.val)||(root.val==q.val))||(lson&&rson)){
//            ans = root;
//        }
//        return lson||rson||root.val==p.val||root.val==q.val;
//    }
}
